Teorema de König (teoría de grafos)

Un ejemplo de un grafo bipartito, con un máximo emparejamiento (azul) y cubrimiento mínimo (rojo) ambos de tamaño seis.

En el área matemática de teoría de grafos, el teorema de König, probado por Dénes Kőnig (1931), describe una equivalencia entre el máximo emparejamiento y el problema de cubrimiento de vértices mínimo en grafos bipartitos. Fue descubierto independientemente, también en 1931, por Jenő Egerváry en el caso más general de grafos con peso.

Descripción

Un grafo es bipartito si sus vértices pueden ser particionados en dos conjuntos tal que cada arista tiene un final en cada conjunto.^[1] Una cubrimiento de vértices en un grafo es un conjunto de vértices que incluye al menos un final de cada arista, y una cubrimiento de vértices es mínimo si ningún otro cubrimiento de vértices tiene menos vértices.^[2] Un emparejamiento en un grafo es un conjunto de aristas ninguna de las cuales comparte un final, y un emparejamiento es máximo si no otro emparejamiento tiene más bordes.^[3] El teorema de König declara que, en cualquier grafo bipartito, el número de aristas en un emparejamiento máximo es igual al número de vértices en un cubrimiento de vértices mínimo.^[4]

Para grafos que no son bipartitos, el máximo emparejamiento y el problema de cubrimiento de vértices mínimo son muy diferentes en complejidad: el emparejamiento máximo puede ser encontrado en tiempo polinómico para cualquier grafo, mientras el cubrimiento de vértices mínimo es NP-completo. El complemento de un cubrimiento de vértices en cualquier grafo es un conjunto independiente, así que un cubrimiento de vértices mínimo es complementario a un conjunto independiente máximo; encontrando los conjuntos independientes máximos es otro problema NP-completo. La equivalencia entre emparejar y cubrir articulado en el teorema de König deja cubrimiento de vértices mínimo y conjuntos independientes máximos para ser computados en tiempo polinómico para grafos bipartitos, a pesar de la NP-Completitud de estos problemas para familias de grafos más generales.^[5]

El teorema de König es equivalente a otros numerosos teoremas de min-max en teoría de grafos y combinatoria, como teorema del matrimonio de Hall y el teorema de Dilworth. Dado que emparejamiento bipartito es un caso especial de flujo máximo, el teorema también es resultado del teorema del corte mínimo.[6]

Historia

El teorema de König está nombrado después del matemático húngaro Dénes Kőnig. Kőnig Había anunciado en 1914 y publicado en 1916 los resultados que cada grafo bipartito regular tiene un emparejamiento perfecto, y más generalmente que el número cromático de cualquier grafo bipartito es igual a su grado máximo^[6] @– la última declaración es conocida comoTeorema de Coloración de la Línea de König .^[7]^[8] Aun así,Bondy y Murty (1976) & Murty (1976) se atribuyó el teorema de König en un papel más tardío de Kőnig (1931). Según Biggs, Lloyd & Wilson (1976), Kőnig atribuyó la idea de estudiar emparejamientos en grafos bipartitos a su padre, matemático Gyula Kőnig. En húngaro, Kőnig el nombre tiene un acento agudo doble, pero su teorema es normalmente deletreado en caracteres alemanes.

Declaración del teorema

En cualquier grafo bipartito, el número de aristas en un emparejamiento máximo es igual al número de vértices en una cubrimiento de vértices mínimo.^[4]

Ejemplo

El grafo bipartito mostrado en la ilustración de arriba tiene 14 vértices; un emparejamiento con seis aristas está mostrado en azule, y un cubrimiento de vértices con seis vértices está mostrada en rojo.No puede haber ningún cubrimiento de vértice más pequeño, porque cualquier cubrimiento de vértice tiene que incluir al menos un final de cada arista emparejada (así como de cada otra arista), así que esto es una cubrimiento de vértice mínimo. De modo parecido, no puede haber ningún emparejamiento más grande , porque cualquier arista emparejada tiene que incluir al menos un final en el cubrimiento de vértices, así que esto es un emparejamiento máximo. El teorema de König declara que la igualdad entre las medidas del emparejamiento y el cubrimiento (en este ejemplo, ambos números son seis) aplica más generalmente a cualquier grafo bipartito.^[4]

Demostración

El teorema de König puede ser probado en una manera que proporciona información útil adicional además de solo su verdad: la prueba proporciona una manera de construir un cubrimiento de vértice mínimo de un máximo emparejamiento. Sea G=(V,E) ser un grafo bipartito, y el conjunto de vértices V sea particionado en un conjunto izquierdo L y un conjunto derecho $R$ . Supongamos que $M$ es un emparejamiento máximo para $G$ . Ningún vértice en una cubrimiento de vértice puede cubrir más de una arista de M, así que si un cubrimiento con |M| vértice puede ser construida, tiene que ser una cubrimiento mínimo.^[9]

Para construir tal cubrimiento, sea $U$ el conjunto de vértices no macheados en $L$ (posiblemente vacío), y sea $Z$ el conjunto de vértices que está en $U$ o está conectado a $U$ por caminos alternos (caminos que alterna entre aristas que están en el emparejamiento y aristas que no están en el emparejamiento ). Sea

K=(L\setminus Z)\cup (R\cap Z).

Cada arista $e$ en $E$ o pertenece a un camino alterno (y tiene un final derecho en $K$ ), o tiene un final izquierdo en $K$ . Luego, si $e$ está emparejado pero no en un camino alterno, entonces su final izquierdo no puede estar en un camino alterno (para tal camino podría solo finalizar en $e$ ) y así pertenecer a $L\setminus Z$ . Alternativamente, si $e$ esta sin emparejar pero no en un camino alterno, entonces su final izquierdo no puede estar en un camino alterno, para tal camino podría ser extendido al añadir $e$ a él. Así $K$ forma un cubrimiento de vértice.^[10]

Además, cada vértice en $K$ es un final de una arista emparejada. Luego, cada vértice en $L\setminus Z$ está emparejado porque Z es un superconjunto de U, el conjunto de vértices izquierdos sin emparejar.Y cada vértice en $R\cap Z$ también tiene que ser emparejado, luego si allí existió un camino alterno a un vértice sin emparejar entonces cambiando el emparejamiento removiendo las aristas emparejadas de este camino y añadiendo las aristas no emparejadas en su lugar incrementaremos el tamaño del emparejamiento. Aun así, ninguna arista emparejada puede tener ambos de su finales en . $K$ Así, $K$ es un cubrimiento de vértices de cardinalidad igual a $M$ , y tiene que ser un cubrimiento de vértices mínimo.^[10]

Algoritmo

La construcción descrita en la prueba encima proporciona un algoritmo para producir un cubrimiento de vértices mínimo dada un emparejamiento máximo . Así, el algoritmo Hopcroft@–Karp para encontrar emparejamientos máximos en grafos bipartitos también puede solucionar el problema de cubrimiento del vértices eficientemente en estos grafos.^[11]

A pesar de la equivalencia de los dos problemas del punto de vista de soluciones exactas, no son equivalentes para algoritmos de aproximación. Emparejamiento Bipartito Máximo puede ser aproximado arbitrariamente con exactitud en tiempo constante por algoritmos distribuidos; en contraste, aproximando el cubrimiento de vértices mínimo de un grafo bipartito requiere al menos tiempo logarítmico.^[12]

Referencias

↑ Bondy y Murty (1976), pp. 4–5.
↑ Called a covering and a minimum covering respectively by Bondy y Murty (1976), p. 73.
↑ Bondy y Murty (1976), p. 70.
↑ ^a ^b ^c Bondy y Murty (1976), Theorem 5.3, p. 74;Cook et al. (2011).
↑ Storer (2001), Exercise 261, p. 342.
↑ Biggs, Lloyd y Wilson (1976).
↑ In a poster displayed at the 1998 International Congress of Mathematicians in Berlin and again at the Bled'07 International Conference on Graph Theory, Harald Gropp has pointed out that the same result already appears in the language of configurations in the 1894 thesis of Ernst Steinitz.
↑ Lovász y Plummer (1986), Theorem 1.4.17, pp. 37ff.
↑ Bondy y Murty (1976), Lemma 5.3, p. 74.
↑ ^a ^b Bondy y Murty (1976), pp. 74–75.
↑ For this algorithm, see Storer (2001), p 319, and for the connection to vertex cover see p. 342.
↑ Göös y Suomela (2012).

Datos: Q897769

[1] Bondy y Murty (1976), pp. 4–5.

[2] Called a covering and a minimum covering respectively by Bondy y Murty (1976), p. 73.

[3] Bondy y Murty (1976), p. 70.

[thm-stmt-4] Bondy y Murty (1976), Theorem 5.3, p. 74;Cook et al. (2011).

[s342-5] Storer (2001), Exercise 261, p. 342.

[6] Biggs, Lloyd y Wilson (1976).

[7] In a poster displayed at the 1998 International Congress of Mathematicians in Berlin and again at the Bled'07 International Conference on Graph Theory, Harald Gropp has pointed out that the same result already appears in the language of configurations in the 1894 thesis of Ernst Steinitz.

[8] Lovász y Plummer (1986), Theorem 1.4.17, pp. 37ff.

[9] Bondy y Murty (1976), Lemma 5.3, p. 74.

[bm-proof-10] Bondy y Murty (1976), pp. 74–75.

[11] For this algorithm, see Storer (2001), p 319, and for the connection to vertex cover see p. 342.

[12] Göös y Suomela (2012).

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]